package chapter6;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 八皇后问题
 *
 * @author yuh
 * @date 2018/4/27 10:47
 */
public class NQueens {

    static boolean[] col = null;
    static boolean[] dia1 = null;
    static boolean[] dia2 = null;
    static List<String> res = new ArrayList<>();

    static void getQueens(int n) {
        col = new boolean[n];
        dia1 = new boolean[2 * n - 1];
        dia2 = new boolean[2 * n - 1];

        //从第一行开始
        putQueens(n, 0, new LinkedList<>());
    }

    private static void putQueens(int n, int rowNum, LinkedList<Integer> points) {
        if (rowNum == n) {
            //已经得到了一个结果
            res.add(getQueensChunk(n, points));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!col[i] && !dia1[rowNum + i] && !dia2[rowNum - i + n - 1]) {
                points.addLast(i);
                col[i] = true;
                dia1[rowNum + i] = true;
                dia2[rowNum - i + n - 1] = true;
                putQueens(n, rowNum + 1, points);
                col[i] = false;
                dia1[rowNum + i] = false;
                dia2[rowNum - i + n - 1] = false;
                points.removeLast();
            }
        }

    }

    private static String getQueensChunk(int n, LinkedList<Integer> points) {
        String str = "";
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j == points.get(i)) {
                    str += "Q";
                } else {
                    str += "●";
                }
            }
            str += "\n";
        }
        return str;
    }

    public static void main(String[] args) {
        getQueens(8);
        for (int i = 0; i < res.size(); i++) {
            System.out.println(res.get(i));
        }
    }
}
